! Kruskal'ın algoritmasının adımlarını görmek için DEVAM düğmesine tıklayınız.

12.7.2. Kruskal'ın Algoritması

Kruskal'ın¹ algoritması en küçük yol ağacını belirlemek için kullanılır; algoritmik ifadesi davranışsal olarak oldukça basittir; ancak gerçeklenmesi için bazı yardımcı fonksiyonlara gerek duyulur. Yandaki canlandırmada 7-düğümlü bir graf üzerinde Kruskal algoritmasının davranışı gösterilmiştir.

Başlangıçta düğümler arasında herhangi bir bağlantı yok gibi düşünülür ve ardından düğümler tek tek ve çevrim oluşturmayacak biçimde bağlanır; eğer bir düğüm çevrim oluşturuyorsa o düğüm atlanır. . adımda en az maliyetli olan, örnekte B-D kenarı, seçilir ve ilgili düğümler birleştirilir; . adımda geride kalan kenarlardan en az maliyetli olan, örnekte F-E, kenarı seçilir ve ilgili düğümler birleştirilir; . adımda, en az maliyetli olan kenar A-B kenarıdır; çevrim oluşturmadığı için bağlanır; . adımda kalanlar arasından en az maliyetli olan A-C seçilir ve eklenir. . adımda F-E seçilir ve bağlanır. . adımda kalan düğümler arasında en az maliyetli olan düğümler, maliyetleri 3 olan, C-E ve G-F düğümleridir. Önce, C-E denenir; çevrim oluşturduğu için atlanır. Daha sonra G-F denenir; çevrim oluşturmadığı için bağlanır; . adımda kapsanmayan düğüm kalmadığı için işlem sonlandırılır. Yol ağacı bulunurken, yolun uzunluğu tane N-1 olur; yani, yol üzerindeki kenar sayısı toplam düğüm sayısından bir eksiktir.